#include "spellchecker.hpp"
#include <string>

using namespace std;

Spellchecker::Spellchecker() :
  _v(new Node)
{}


void Spellchecker::insert(string s) {
  insert_aux(_v, s, 0);
}

void Spellchecker::insert_aux(Node *v, string s, unsigned i) {
  if (i >= s.size()) return;

  int inx = index(s[i]);
  
  // reach the end of the word
  if (i == s.size()-1) {
    v->_is_w[inx] = true;
    return;
  }

  // intermediate step
  if (v->_child[inx] == NULL) {
    v->_child[inx] = new Node;
  }
  insert_aux(v->_child[inx], s, i+1);
}

bool Spellchecker::is_word(string s) {
  return is_word_aux(s, 0, _v);
}

bool Spellchecker::is_word_aux(string s, int i, Node *node) {
  int inx = index(s[i]);
  if (i == s.size()-1) {
    return node->is_w(inx);
  }

  if (node->_child[inx] == NULL) return false;
  return is_word_aux(s, i+1, node->_child[inx]);
}

vector<string> Spellchecker::get_suggestion(string s) {
    vector<string> ret = get_sug_aux(_v, s, 0, "", false);

    if (ret.size() == 0) {
	string tmp = get_next_w(s);
	if (tmp.size() > 0) {
	    ret.push_back(tmp);
	}
    }
    
    if (ret.size() == 1) {
	string tmp = get_next_w(ret[0]);
	if (tmp.size() > 0) {
	    ret.push_back(tmp);
	}
    }
    
    return ret;
}


vector<string> Spellchecker::get_sug_aux(Node * node,
                                         string s, 
                                         int    i, 
                                         string hd, 
                                         bool   crd) {
    vector<string> ret;

    if (crd) {
	if (is_word_aux(s, i, node)) {
	    for (;i<s.size(); i++) {
		hd += s[i];
	    }
	    ret.push_back(hd);
	}
    } else if(i == s.size()) {
	for (int k=0; k<DLEN; k++) {
	    if (node->is_w(k)) {
		ret.push_back(hd + get_char(k));
	    }
	}
    } else {
	int inx = index(s[i]);
	for (int k=0; k<DLEN; k++) {
	    if (node->_child[k] != NULL) {
		vector<string> tmp = get_sug_aux(node->_child[k],
						 s, i+1,
						 hd+get_char(k),
						 !(k == inx));
		if (tmp.size() > 0)
		    ret.insert(ret.end(), tmp.begin(), tmp.end());
	    }
	}
    }
  
    return ret;
}


string Spellchecker::get_next_w(string s) {
    Node *node = _v;
    if (s.size() == 0) return get_first_w(_v, "");

    int i=0;

    string ret;
    for (; i<s.size()-1; i++) {
	int inx = index(s[i]);
	if (node->_child[inx] != NULL) {
	    ret += s[i];
	    node = node->_child[inx];
	} else {
	    break;
	}
    }

    int inx = index(s[i]) + 1;
    
    for (inx; inx<DLEN; inx++) {
	if (node->is_w(inx)) {
	    ret += get_char(inx);
	    return ret;
	} 
	
	if (node->_child[inx] != NULL) {
	    ret += get_char(inx);
	    ret = get_first_w(node->_child[inx], ret);
	    return ret;
	}
    }

    string tmp(s, 0, s.size()-1);
    return get_next_w(tmp);
}

string Spellchecker::get_first_w(Node *node, string s) {
    if (node == NULL) return "";

    for (int i=0; i<DLEN; i++) {
	if (node->is_w(i)) {
	    return s+get_char(i);
	}

	if (node->_child[i] != NULL) {
	    return get_first_w(node->_child[i], s+get_char(i));
	}
    }
    
    return "";
}


// Class : Node
Node::Node() {
  for (int i=0; i<DLEN; i++) {
    _is_w[i]  = false;
    _child[i] = NULL;
  }
}
